package dp;

//换钱的最少货币数
public class CoinChange {

	public static void main(String[] args) {
//		System.out.println(coinChange(new int[]{186, 419, 83, 408}, 6249));
		System.out.println(coinChangeCount2(new int[]{1, 2, 5}, 5));
	}
	
	//经典的dp问题
	//dp[i][j] 表示在使用coins[0...i]的时候，组成j所需的最小张数
	//dp[i - 1][j]表示不使用coin[i]中的货币
	//dp[i][j - coin[i]] + 1表示coin[i]中的货币，等于之前计算的dp[i][j - coin[i] ] 再加上i这一张
	//dp[i][j] = min {dp[i - 1][j], dp[i][j - coin[i]] + 1} ( j >= coin[i]) 如果小于说明j太小了
	
	//对于coins中的货币可以使用多次
    public static int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length <= 0 || amount < 0){
        	return -1;
        }
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];
        //dp[0][j]只能是那些j为coin[0]整数倍的有值，其他的置为max_value
        for (int j = 1; j < dp[0].length; j++) {
			dp[0][j] = Integer.MAX_VALUE;
			if(j % coins[0] == 0){
				dp[0][j] = j / coins[0];
			}
		}
        int left = Integer.MAX_VALUE;
        for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j < dp[0].length; j++) {
				left = Integer.MAX_VALUE;  //注意每次要重新置位
				//dp[i][j - coins[i]] = Integer.MAX_VALUE表示无法组成该货币值
				if( j >= coins[i] && dp[i][j - coins[i]] != Integer.MAX_VALUE){
					left = dp[i][j - coins[i]] + 1;
				}
				dp[i][j] = Math.min(left, dp[i - 1][j]);
			}
		}
        for (int i = n - 1; i < n; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				if(j > 0 && j % 10 == 0){
					System.out.println();
				}else {
					System.out.print(dp[i][j] + " ");
				}
			}
			System.out.println();
		}
        return dp[n - 1][amount] != Integer.MAX_VALUE ? dp[n - 1][amount] : -1;
    }
    
    //对于coins中的货币，只能使用1次
    public static int coinChange2(int[] coins, int amount) {
        if(coins == null || coins.length <= 0 || amount < 0){
        	return -1;
        }
        int n = coins.length;
        int[][] dp = new int[n][amount + 1];
        for (int j = 0; j < dp[0].length; j++) {
			dp[0][j] = Integer.MAX_VALUE;
		}
        if (coins[0] <= amount) {
			dp[0][coins[0]] = 1;  //由于只能使用一次,注意coins[0]可能大于数组的边界
		}
        //其他的情况不变，还是等于不使用coins[i]以及使用coins[i]之后的最小值
        int left = Integer.MAX_VALUE;
        for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j < dp[0].length; j++) {
				left = Integer.MAX_VALUE;  //注意每次要重新置位
				//dp[i][j - coins[i]] = Integer.MAX_VALUE表示无法组成该货币值
				if( j >= coins[i] && dp[i][j - coins[i]] != Integer.MAX_VALUE){
					left = dp[i][j - coins[i]] + 1;
				}
				dp[i][j] = Math.min(left, dp[i - 1][j]);
			}
		}
        for (int i = n - 1; i < n; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				if(j % 10 == 0){
					System.out.println();
				}else {
					System.out.print(dp[i][j] + " ");
				}
			}
			System.out.println();
		}
        return dp[n - 1][amount] != Integer.MAX_VALUE ? dp[n - 1][amount] : -1;
    }
    
    //计算能够换算aim钱币的方法总数
    //每种钱币可以使用多次
    //dp[i][j] 表示使用coins[0 ...i]构成钱币j的方法总数
    //dp[i][0] = 1 ,构成0元的方法数为1，代表不使用任何钱币
    //dp[0][...] = 1 ,while j = n * coins[0] 其他情况为0 
    //dp[i][j] = dp[i - 1][j](完全不使用coin[i]) + dp[i - 1][j - arr[i]] + dp[i - 1][j - 2 * arr[i]]  + ....
    //dp[i - 1][j - arr[i]] + dp[i - 1][j - 2 * arr[i]]  +....表示分别使用1张，2张...n张coins[i]时的方法数
    //n * arr[i] <= j
    public static int coinChangeCount(int[] arr, int aim){
    	if(arr == null || arr.length <= 0){
    		return 0;
    	}
    	int[][] dp = new int[arr.length][aim + 1];
    	for (int i = 0; i < dp.length; i++) {
			dp[i][0] = 1;
		}
    	for (int j = 0; j < dp[0].length; j++) {
			if(j % arr[0] == 0){
				dp[0][j] = 1;
			}
		}
    	int num = 0;
    	for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j < dp[0].length; j++) {
				num = 0;
				for (int k = 0; k * arr[i] <= j; k++) {
					num += dp[i - 1][j - k * arr[i]];
				}
				dp[i][j] = num;
			}
		}
    	return dp[arr.length - 1][aim];
    }
    
    //after 优化
    //dp[i - 1][j - arr[i]] + dp[i - 1][j - 2 * arr[i]]  +....表示分别使用1张，2张...n张coins[i]时的方法数
    //其实就是等于dp[i][j - arr[i]]
    public static int coinChangeCount2(int[] arr, int aim){
    	if(arr == null || arr.length <= 0){
    		return 0;
    	}
    	int[][] dp = new int[arr.length][aim + 1];
    	for (int i = 0; i < dp.length; i++) {
			dp[i][0] = 1;
		}
    	for (int j = 0; j < dp[0].length; j++) {
			if(j % arr[0] == 0){
				dp[0][j] = 1;
			}
		}
    	int num = 0;
    	for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j < dp[0].length; j++) {
				num = dp[i - 1][j];
				num += j >= arr[i] ? dp[i][j - arr[i]] : 0;
				dp[i][j] = num;
			}
		}
    	return dp[arr.length - 1][aim];
    }
}
